import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-19
 * Time: 22:57
 */
public class Solution {
    public int length;//记录数字字符串的长度
    public StringBuilder stringBuilder=new StringBuilder();//记录字符
    public List<String> ans=new ArrayList<>();//结果

    //递归回溯
    //表示固定了第几位字符
    public void dfs(String digits,int x){
        if(x>=length){
            //递归完了
            return ;
        }
        int num=Integer.parseInt(digits.charAt(x)+"");
        //得到数字对应的字符串
        String str=getString(num);
        for(int i=0;i<str.length();i++){
            char ch=str.charAt(i);
            //添加字符
            stringBuilder.append(ch+"");
            if(x==this.length-1){
                //递归到最后一个字符了就添加到结果中
                this.ans.add(stringBuilder.toString());
            }else{
                //递归
                dfs(digits,x+1);
            }
            //递归完,弹出最后一个字符
            stringBuilder.deleteCharAt(x);
        }
    }


    //得到数字对应的字符串
    public String getString(int num){
        switch(num){
            case 2:return "abc";
            case 3:return "def";
            case 4:return "ghi";
            case 5:return "jkl";
            case 6:return "mno";
            case 7:return "pqrs";
            case 8:return "tuv";
            case 9:return "wxyz";
        }
        return "";
    }

    public List<String> letterCombinations(String digits) {
        this.length=digits.length();
        dfs(digits,0);
        return this.ans;
    }
}
